/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if(!A || !B)  return false;
        /*
        2020/11/25 1刷
        先从A中找到和B头结点一样的结点值，再判断两者的结构是否一样
        若val类型为double等，则在进行值对比时应当考虑使用equal()等而不是直接使用“==”
        */
        return findTheSamePointer(A, B);

    }

    //用递归遍历数组
    bool findTheSamePointer(TreeNode* A, TreeNode* B){
        bool beFund = false;
        if((A->val == B->val) && isSame(A, B))  return true;
        if(A->left)  beFund |= findTheSamePointer(A->left, B);
        if(!beFund && A->right)    beFund |= findTheSamePointer(A->right, B);
        return beFund;  //只要在左右子树任一边找到就可以返回true
    }

    //用递归判断两子树是否一样
    bool isSame(TreeNode* A, TreeNode* B){
        bool isTrue = true;
        if(!A || (A->val != B->val))  return false;
        if(B->left)  isTrue &= isSame(A->left, B->left);
        if(isTrue && B->right)  isTrue &= isSame(A->right, B->right);
        return isTrue;  //左右子树均相等才能返回true
    }
};